package com.hp;

/**
 * 简易的queue
 * 队列是一种基于先进先出（FIFO)策略的线性数据结构。
 * 这就像在学校食堂买饭排队一样，排在前面的人先打饭，后面的人后打饭。
 * 该模板只有6个方法，分别是isEmpty(),size(),front(),back(),pop(),push(T).
 * 代码如下:
 * @author haopeng
 * @date 2019-04-04 16:02
 */
public class Queue<Item> {

    private Node first;
    private Node last;
    private int N;

    private class Node {
        Item item;
        Node next;
    }

    public boolean isEmpty() {            //判断是否为空
        return this.first == null;
    }

    public int size() {                //队列的大小
        return N;
    }

    public void push(Item T) {            //向队列添加元素
        Node temp = last;
        last = new Node();
        last.item = T;
        last.next = null;
        if (isEmpty())
            first = last;
        else
            temp.next = last;
        N++;
    }

    public Item pop() {        //弹出第一个元素，并返回第一个元素
        Node temp = first;
        first = first.next;
        if (isEmpty())
            last = null;
        N--;
        return temp.item;
    }

    public Item front() {        //访问队列第一个元素
        return first.item;
    }

    public Item back() {
        return last.item;//访问队列最后一个元素
    }

    public static void main(String[] args) {
        Queue<String> sb = new Queue<String>();
        sb.push("hi");
        if (sb.isEmpty())
            System.out.println("isEmpty!");
        else System.out.println("NotEmpty!");
        sb.push("hello");
        sb.push("world");
        System.out.println(sb.front());
        System.out.println(sb.pop());
        System.out.println(sb.back());
        System.out.println(sb.pop());
        System.out.println(sb.pop());
        if (sb.isEmpty())
            System.out.println("isEmpty!");
        else System.out.println("NotEmpty!");
    }

}
